Introduzione
Un Problema di Ottimizzazione consiste nel trovare una x \in X \sube \mathbb{R}^n che minimizza o massimizza una certa funzione, detta Funzione Obiettivo, dove X è detto Insieme Ammissibile.
Per risolvere un problema di ottimizzazione bisogna quindi trovare una x^* tale per cui x^* \in X e f(x^*) è minimo o massimo.
x^* \in \mathbb{R}^n è ottimo globale se x^* \in X e \not \exists \bar x \in X : f(\bar x) \lt f(x^*).
x^* \in \mathbb{R} è un ottimo locale se x^* \in X e \exists \varepsilon \gt 0 : \not \exists \overline x \in \mathcal{N}_\varepsilon(x^*) \cap X : f(\overline x) \lt f(x^*)
La notazione
\begin{align*} \min & \qquad f(x) \\ \text{s.t.} & \qquad x \in X \end{align*}
è completamente equivalente alla notazione
\min\left\{ f(x) : x \in X \right\}
e possono essere utilizzate interscambievolmente.
Modelli di ottimizzazione
Il modello di un problema (ovvero la rappresentazione matematica di un problema reale) è composto da variabili, vincoli e funzione obiettivo.
Le variabili sono quelle che descrivono la decisione che deve essere presa.
I vincoli sono le restrizioni si tali variabili e possono essere di tre tipi:
- vincoli fisici (ad esempio la capacità di un rimorchio)
- vincoli di tipo (ad esempio nonnegatività o appartenenza ad un certo dominio)
- vincoli legali (tutti quelli che ci sono perchè sta scritto così)
La funzione obiettivo è una funzione che dipende dalle decisioni che deve essere minimizzata (o massimizzata).
Supponiamo di voler costruire una lattina cilindrica standard da 330 ml che sia composta dalla minor quantità di alluminio.
Le variabili in gioco sono r (il raggio della lattina) e h (l’altezza della lattina).
Il vincolo da rispettare è \pi r^2 h = 330 ml con r \ge 0 e h \ge 0 (i vincoli stretti non si possono utilizzare per motivi che vedremo più avanti anche se è palese che una lattina di raggio nullo, in questo contesto, sarebbe una soluzione non valida).
La funzione obiettivo da minimizzare è l’area della lattina ovvero 2 \pi r^2 + 2 \pi hr.
Formalmente, un problema di minimopuò essere espresso come problema di massimo e viceversa:
\min \{ f(x) : x \in X \} = - \max \{ -f(x) : x \in X \}
Ne segue che tutto ciò che è applicabile su un problema di un tipo può essere applicato anche su problemi del tipo inverso con le divute accortezze.
Problemi di ottimizzazione
Sia P un problema generico del tipo \min \{ f(x) : x \in X \}.
P si dice inammissibile X = \emptyset.
P si dice illimitato se x \ne \emptyset e \forall M \lt 0 \exists \bar x \in X : f(\bar x) \le M.
In altre parole, un problema è illimitato non se non ci sono soluzioni ma se, presa una qualunque soluzione, ce n’è sempre una migliore.
Rilassamento di un problema di ottimizzazione
Dato un generico problema di ottimizzazione
\begin{align*} \min & \qquad f(x) \\ \text{s.t.} & \qquad x \in X \end{align*}
un rilassamento è un altro problema di ottimizzazione del tipo
\begin{align*} \min & \qquad \tilde f(x) \\ \text{s.t.} & \qquad x \in \tilde X \end{align*}
tale che 1. \tilde X \supseteq X 2. \forall x \in X \quad \tilde f(x) \le f(x)
La definizione è analoga per problemi di massimo se nella seconda condizione si usa \ge.
Nella pratica, un rilassamento di un problema è tale se i vincoli sono più tenui ma le soluzioni sono migliori.
Siano P un problema di minimo \min \left\{f(x) : x \in X\right\} e R un suo rilassamento \min\left\{ \tilde f(x) : x \in \tilde X \right\}, allora è possibile esprimere alcune proprietà di cui il rilassamento gode:
- Se x^* è ottimo per P allora x^* è ammissibile per \tilde x ma non è necessariamente ottimo per R.
- Se x^* è ottimo per R allora non è necessariamente ammissibile (e quindi nemmeno ottimo) per P.
- Se x^* è ottimo per R e ammissibile per P allora x^* non è necessariamente ottimo per P, a meno che non si abbia che anche f(x^*) = \tilde f(x^*); in tal caso allora x^* è anche ottimo per P.
Analisi convessa
Sia dato un insieme di m vettori x^i \in \mathbb{R}^n \forall i \in M = \{ 1, \dots, m \}, allora
Dati m scalari \lambda_i \ \forall i \in M, \sum\limits_{i \in M} \lambda_iv^i \in \mathbb{R} è
- una combinazione lineare se \lambda_i \in \mathbb{R} \forall i \in M
- una combinazione affine se \sum\limits_{i \in M} \lambda_i = 1
- una combinazione conica se \lambda_i \ge 0 \forall i \in M
- una combinazione convessa se è sia affine che conica
Dati m punti x^1, x^2, \dots, x^m \in \mathbb{R}^n, lo span lineare di x^1, x^2, \dots, x^m è l’insieme di tutte le combinazioni lineari di x^1, x^2, \dots, x^m costruite con coefficienti \lambda_i \in \mathbb{R}.
Dati m punti x^1, x^2, \dots, x^m \in \mathbb{B}^n, lo span affine di x^1, x^2, \dots, x^m è l’insieme di tutte le combinazioni affini di x^1, x^2, \dots, x^m.
Matematicamente, lo span affine di un insieme di punti x^1, x^2, \dots, x^m può essere definito come
\left\{ \sum_{i=1}^m \lambda_i x^i : \sum_{i=1}^m \lambda_i = 1 \right\}
Dati m punti x^1, x^2, \dots, x^m \in \mathbb{R}^n, l’inviluppo conico di x^1, x^2, \dots, x^m è l’insieme di tutte le combinazioni coniche di x^1, x^2, \dots, x^m.
Matematicamente, l’inviluppo conico di x^1, x^2, \dots, x^m può essere descritto come
\left\{ \sum_{i=1}^m \lambda_ix^i : \lambda_i \ge 0 \ \forall i = i \dots m \right\}
e rappresenta la minima piramide con vertice nell’origine e base all’infinito che contiene tutti i punti dati.
Intersecando lo span affine e l’inviluppo conico, si ottiene l’inviluppo complesso.
Dati m punti x^1, x^2, \dots, x^m \in \mathbb{R}^n, l’inviluppo convesso di x^1, x^2, \dots, x^m è l’insieme di tutte le combinazioni convesse di x^1, x^2, \dots, x^m.
Matematicamente, l’inviluppo complesso di un insieme di punti x^1, x^2, \dots, x^m può essere descritto dall’intersezione dell’insieme dhe descrive lo span affine con quello che descrive l’inviluppo conico:
\left\{ \sum_{i=1}^m \lambda_ix^i : \lambda_i \ge 0 \ \forall i = 1, \dots, m, \ \sum_{i=1}^m \lambda_i = 1 \right\}
Come si pu osservare trascinando i punti nell’embed qui sotto, l’inviluppo convesso di un insieme di punti è il minimo luogo convesso dello spazio che contiene tutti i punti dati (un po’ come mettere un elastico n-dimesionale attorno ai punti dati).
Funzioni convesse
Una funzione f : \mathbb{R}^n \to \mathbb{R} è convessa se \forall x',x'' \in \mathbb{R}^n,\forall \lambda \in [0,1] vale che f(\underbrace{\lambda x' + (1 - \lambda)x''}_{\text{combinazione convessa}}) \le \lambda f(x') + (1-\lambda)f(x'').
In generale, sia \sum\limits_{i=1}^m \lambda_i x^i una combinazione convessa, allora una funzione è convessa se
f\left(\sum_{i=1}^m \lambda_i x^i\right) \le \sum_{i=1}^m \lambda_i f(x^i)
Le funzioni convesse godono di alcune proprietà (che possono essere dimostrate tutte con la definizione):
- La somma di funzioni convesse è a sua volta convessa.
- Il prodotto di uno scalare non negativo per una funzione convessa è a sua volta convesso.
- Il massimo tra funzioni convesse è a sua volta una funzione convessa.
Una funzione f è concava se e solo se -f è convessa.
Una funzione lineare è sia concava che convessa.
Una forma quadratica x^TQx è convessa se Q è semidefinita positiva.
Un insieme S \sube \mathbb{R}^n è convesso se \forall x', x'' \in S, \forall \lambda \in [0,1] vale che \lambda x' + (1 - \lambda)x'' \in S.
Gli insiemi convessi godono di alcune proprietà:
- L’intersezione di insiemi convessi è a sua volta convessa (non vale per l’unione).
- Un insieme definito come S = \left\{ x \in \mathbb{R}^n : g(x) \le \alpha \right\} con g convessa è a sua volta convesso.
- Un insieme definito come S = \left\{x \in \mathbb{R}^n : g(x) \ge \alpha \right\} con g concava è convesso.
Dalle prime due proprietà appena citate, segue che se per ciascun vincolo di un problema dato costruisco un insieme che lo rispetta, se poi interseco tutti questi insiemi, ho l’insieme degli elementi ammissibili per tale problema.
Un problema \min \{f(x) : x \in X\} è convesso se f è una funzione convessa e X è un insieme convesso.
Analogamente, se ho un problema come quello nella definizione ma di massimo, tale problema rimane convesso se f è concava (X deve rimanere convesso).
Complessità computazionale
Ci sono varie categorie di problemi: alcuni esempi possono essere il problema dello zaino, il problema di ottimizzazione lineare, il sudoku e la ricerca del cammino minimo.
Dato che questi problemi sono di categorie standard, è possibile definire una soluzione parametrica che si applica indiscriminatamente a tutti i problemi del tipo a cui si riferisce.
Un’istanza di un problema è uno specifico problema di una certa categoria nel quale sono stati assegnati dei valori ai parametri.
Un algoritmo è una sequenza di passi elementari tali per cui, dati i parametri di un’istanza di un problema, seguendoli è possibile arrivare in alla soluzione per il problema di cui sono stati dati i parametri.
Una definizione più precisa di algoritmo è disponibile sotto.
Problemi facili e problemi difficili
Per valutare quanto è facile o meno risolvere un problema con un determinato algoritmo, si può procedere in diversi modi:
- si può misurare il tempo di esecuzione di un programma che implementa tale algoritmo (o cronometrarsi mentre lo si esegue a mano);
- per una misura più oggettiva, si possono contare il numero di operazioni elementari necessarie per risolvere un’istanza di dimensione n (in tal modo il risultato non cambia anche cambiando processore o utilizzando tecniche di parallelizzazione);
Per il secondo punto, si utilizza una funzione nel dominio delle istanze che restituisce un numero naturale (il numero di passi elementari che servono per risolvere tale istanza).
La complessità computazionale si occupa del worst-case scenario.
Dato un problema \Pi e un insieme di istanze di \Pi di dimensione n, la complessità computazionale di tale problema è pari alla complessità del miglior algoritmo (ovvero quello che ci dà la minima complessità) A che risolve tutte le istanze di \Pi date.
Se per un dato problema non è disponibile nessun algoritmo che possa risolvere in modo efficiente tale problema, allora esso è un problema difficile. Se esiste anche un solo algoritmo che consenta di risolvere tale problema in maniera efficiente, allora basta utilizzare tale algoritmo e posso dire che il problema è semplice.
Tutti gli studi sull’analisi della complessità computazionale non sono stati fatti su problemi di ottimizzazione, bensì su problemi di riconoscimento.
Problemi di riconoscimento
Un problema è detto di riconoscimento o di ammissibilità se non si vuole minimizzare nulla ma solo sapere se esiste una soluzione.
Un problema di riconoscimento \Pi è definito da
- un insieme di istanze;
- una domanda la cui risposta è si/no.
E’ possibile trasformare un problema di ottimizzazione nel suo corrispondente problema di riconoscimento: dato il problema di ottimizzazione generico
\begin{align} \min \qquad & f(x) \\ \text{s.t.} \qquad & x \in X \end{align}
il suo corrispondente problema di riconoscimento è “Data la tripla (f, X, \beta), allora \exists x \in X : f(x) \le \beta?”.
L’analogo per un problema di massimizzazione è dato dall’utilizzo del \ge al posto del \le.
Istanze di un problema di riconoscimento
Siano dati un problema di riconoscimento \Pi e i seguenti insiemi:
- D_\Pi: l’insieme delle istanze di \Pi;
- Y_\Pi: il sottoinsieme delle istanze di \Pi con risposta affermativa.
Sia \Sigma un insieme di simboli e \Sigma^* l’insieme di tutte le stringhe sull’alfabeto \Sigma.
Una codifica e di un problema \Pi è una funzione e : D_\Pi \to \Sigma^*.
Dato un problema \Pi ed una codifica e allora è possibile partizionare l’insieme \Sigma^* in tre sottoinsiemi:
- l’insieme delle stringhe s = e(I) : I \not \in D_\Pi (ovvero l’insieme delle stringhe che possono essere interpretate come un’istanza non valida);
- l’insieme delle stringhe s = e(I) : I \in D_\Pi - Y_\Pi;
- l’insieme delle stringhe s = e(I) : I \in Y_\Pi.
Un linguaggio L(\Pi, e) è un insieme di stringhe L(\Pi, e) = \{x \in \Sigma^* : e \text{ usa } \Sigma^*, x = e(I) \ \forall I \in Y_\Pi \}.
Una volta date tutte queste definizioni, è possibile dare una definizione più precisa di algoritmo.
Un algoritmo M che lavora con l’alfabeto \Sigma accetta x \in \Sigma^* se M termina con risposta positiva quando eseguito su x.
Il linguaggio L_M riconosciuto da M è definito come
L_M = \{x \in \Sigma^* : M \text{ accetta } x\}
La lunghezza (lenght) è una funzione indipendente dalla codifica che lega la codifica di un’istanza all’istanza vera e propria:
\text{Lenght} : D_\pi \to \mathbb{Z}^+
Tale funzione ha una relazione polinomiale, ovvero
\exists p_1, p_2 \in \mathbb{R}[x] : \forall I \in D_\pi : x = e(I) \qquad \begin{cases} \text{Lenght}(I) \le p_1(|x|) \\ |x| \le p_2(\text{Lenght(I)}) \end{cases}
Funzioni di complessità
Dato un algoritmo M e n \in \mathbb{Z}^+
T_M(n) = \max\left\{ m : \exists x \in \Sigma^* : |x| = n \text{ tale che $M$ applicato a $x$ termina in $m$ passi} \right\}
in pratica, stiamo cercando l’istanza di un dato problema che fa impiegare più tempo all’algoritmo che lo risolve (worst-case scenario).
Non è interessante il numero di passi che serve ad un algoritmo per risolvere un problema quanto il modo in cui questo numero varia al variare della lunghezza dell’istanza.
Un algoritmo è a tempo polinomiale se \exists p : \mathbb{Z}^+ \to \mathbb{Z}^+ tale che T_M(n) \le p(n) \forall n \in \mathbb{Z}^+.
Non è interessante nemmeno la variazione precisa, basta il comportamento asintotico.
f : \mathbb{Z}^+ \to \mathbb{Z}^+ \in O(n) con g : \mathbb{Z}^+ \to \mathbb{Z}^n se \exists c \gt 0, n_0 \in \mathbb{Z}^+ : f(n) \le g(n) \ \forall n \ge n_0.
Anche complessità come O(n \log n) sono considerate polinomiali in quanto O(n \log n) \simeq O(n^{1+\varepsilon}).
P vs. NP
Un problema è detto P se è risolvibile in tempo polinomiale mentre, un problema è detto NP (Non-deterministic Polynomial) se ammettono almeno un algoritmo non deterministico che lo risolve.
In questo contesto un algoritmo non deterministico M con I \in D_\pi consiste nell’estrarre a caso una struttura S per poi determinare in tempo polinomiale se (S, I) \in Y_\pi.
Un problema P è semplice mentre i NP sono un po’ meno semplici, però hanno anche un vantaggio: esiste sempre un modo per verificare in tempo polinomiale se una data soluzione è soluzione di un problema o meno.
Si possono dare definizioni di P e NP più formali:
P = \{L : \exists \text{ algoritmo } M \text{ polinomiale} : L = L_M\}
NP = \{L : \exists \text{ algoritmo } M \text{ polinomiale non deterministico} : L = L_M\}
Esiste un algoritmo per risolvere i problemi NP: per ogni problema \pi \in NP, esiste un polinomio p : \mathbb{Z}^+ \to \mathbb{Z}^+ tale che esiste un algoritmo M di complessità O(2^{p(n)}) per ogni I \in D_\pi : |e(I)| = n. Tale algoritmo consiste nel provare a forza bruta tutte le possibili soluzioni.
P \sube NP
Problemi quali la fattorizzazione di n interi e l’ottimizzazione lineare intera sono problemi NP.
Problemi difficili perchè nessuno li ha ancora risolti
Si può ridurre un problema \pi_1 ad un problema \pi_2 se esiste un algoritmo che traduce un’istanza di \pi_1 in un’istanza di \pi_2 in un tempo polinomiale.
Dati \pi_1, \pi_2, si dice che “\pi_1 si riduce a \pi_2” (\pi_1 \propto \pi_2) se esiste un algoritmo A : T_A(n) \in O(p(n)) per un polinomio p che, data un’istanza I \in D_{\pi_1}, ritorna un’istanza I' \in D_{\pi_2}.
Da questo seguono alcune proprietà:
- se \pi_2 \in P e \pi_1 \propto \pi_2 allora \pi_1 \in P;
- se \pi_1 \propto \pi_2 allora \pi_2 è difficile almeno quanto \pi_1 o, viceversa, \pi_1 è almeno facile quanto \pi_2.
NPC è l’insieme di problemi \pi tali che - \pi \in NP - \forall \pi' \in NP \ \pi' \propto \pi
Dato un insieme di n variabili y_1, y_2, \dots, y_n \in \{T, F\} ed un insieme di clausole C_1, C_2, \dots, C_n definite come disgiunzione di 3 variabili (o, eventualmente, negazioni di esse), esiste un assegnamento di variabili tale che tutte le clausole siano vere?
Il fatto che tale problema sia stato trovato ci dice che NPC \ne \emptyset. Dato che Sat3 è un problema NPC, tutti i problemi NP possono essere ridotti a Sat3 dunque, se si trovasse un algoritmo che risolve Sat3 in tempo polinomiale, avremmo dimostrato che P = NP.
Per dimostrare che un determinato problema è NPC si deve prendere un altro NPC (ad esempio, Sat3) e ridurlo al problema sotto esame.
Il problema di ottimizzazione lineare intera (ILO) è NPC in quanto esiste un algoritmo che, in tempo polinomiale, trasforma un’istanza di Sat3 in un’istanza di ILO. Segue dimostrazione.
L’algoritmo in questione è A_2.
Data un’istanza Sat3 con n variabili y_1, y_2, \dots, y_n e m clausole C_1, C_2, \dots, C_n, creo n variabili booleane x_1, x_2, \dots, x_n e traduco ciascuna clausola nel suo equivalente vincolo lineare come visto qui (a ciascuna y_i associo x_i). La funzione obiettivo c è inutile quindi pongo c \equiv 0.
Ottimizzazione lineare
L’ottimizzazione lineare spesso approssima il modello su cui lavorare perchè il mondo reale contiene molte non linearità, però rende molto più semplici i conti.
Una funzione f : \mathbb{R}^n \to \mathbb{R} è lineare se è della forma f(x) = \sum\limits_{i=1}^n a_ix_i.
Dalle proprietà delle funzioni convesse e dalle proprietà degli insiemi convessi segue che gli insiemi della forma S = \left\{x \in \mathbb{R}^n : \sum\limits_{i=1}^n a_ix_i \gtreqless b\right\} è un insieme convesso.
I problemi della forma
\begin{align*} \min \qquad & c_1x_1 + c_2x_2 + \dots + c_nx_n \\ \text{s.t.} \qquad & a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \le b_1 \\ & a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \le b_2 \\ & \qquad \vdots \\ & a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \le b_n \end{align*}
sono detti problemi di ottimizzazione lineare e possono essere espressi come
\begin{align*} \min \qquad & c_1x_1 + c_2x_2 + \dots + c_nx_n \\ \text{s.t.} \qquad & \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \le \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix} \end{align*}
Ottimizzazione lieare intera
Un problema di ottimizzazione lineare intera è esattamente come un problema di ottimizzazione lineare, tranne che ha vincoli aggiuntivi della forma x_i \in \mathbb{Z} \ \forall i \in I \subseteq \{1, \dots, n\} e/o vincoli della forma x_i \in \{0, 1\} \ \forall i \in I \subseteq \{1, \dots, n\} (le variabili vincolate in questo modo vengono dette variabili booleane).
Variabili booleane
Un ladro deve rubare oggetti da una casa. Ciascun oggetto ha un valore e un peso associati, lo zaino del ladro ha una capacità massima che non può essere superata. Si vuole trovare la combinazione di oggetti che massimizzi il valore portato a casa. I parametri di questo problema sono:
- v_i: il valore dell’oggetto i-esimo;
- p_i: il peso dell’oggetto i-esimo;
- c: la capacità dello zaino.
Le variabili da trovare per questo problema sono:
- x_i \in \{0, 1\}: indica se l’oggetto i-esimo è da prendere (x_i = 1) o meno (x_i = 0).
Il problema da ottimizzare è dunque
\begin{align*} \max \qquad & \sum_{i=1}^n v_ix_i \\ \text{s.t.} \qquad & \sum_{i=1}^n p_ix_i \le c \\ & x_i \in \{0, 1\} \quad \forall i = {1, \dots, n} \end{align*}
Immaginiamo che alcuni oggetti siano inutili se rubati da soli e che dunque vadano rubati insieme ad altri o che due oggetti, per qualche motivo, non possano essere rubati e messi nello zaino assieme (ad esempio una sfera di plutonio ed un pezzo di carburo di tungsteno): vengono aggiunti dei vincoli aggiuntivi a titolo di esempio (assumendo che n sia abbastanza grande).
- Se viene rubato l’oggetto 1, allora si devono rubare anche gli oggetti 7 e 8;
- Se viene rubato l’oggetto 3, allora non deve essere rubato l’oggetto 5;
- Se vengono rubati gli oggetti 4 e 6 assieme, allora deve essere rubato anche l’oggetto 5;
- Se vengono rubati gli oggetti 1 e 3 assieme, allora non deve essere rubato l’oggetto 8;
- Viene rubato l’oggetto 4 se e solo se viene rubato l’oggetto 7.
Tutti i vincoli sulle variabili booleane sono esprimibili in maniera abbastanza intuitiva e standard (tranne qualche caso): solitamente basta sostituire il “\implies” con il “\le” e le “x_i = 0” con (1 - x_i) e lavorare un po’ con le proprietà della logica per arrivare ad una funzione lineare utilizzabile nei vincoli. Segue tabella con esempi di conversioni.
| Vincolo logico | Vincolo lineare |
|---|---|
| x_1 = 1 \implies x_2 = 1 | x_1 \le x_2 |
| x_1 = 1 \implies x_2 = 0 | x_1 \le 1 - x_2 |
| x_1 = 0 \implies x_2 = 0 | 1 - x_1 \le 1 - x_2 \equiv x_2 \le x_1 |
| x_1 = 1 \lor x_2 = 1 | x_1 + x_2 > 1 |
| x_1 = 0 \lor x_2 = 1 | (1 - x_1) + x_2 \ge 1 \equiv x_1 \le x_2 |
| x_1 = 0 \land x_2 = 1 | \begin{cases} x_1 = 0 \\ x_2 = 0 \end{cases} |
| (x_1 = 1 \land x_2 = 1) \implies x_3 = 1 | x_3 \ge x_1 + x_2 - 1 |
| (x_1 = 0 \land x_2 = 1) \implies x_3 = 1 | x_3 \ge (1 - x_1) + x_2 -1 |
| x_1 = 1 \oplus x_2 = 1 | x_1 + x_2 = 1 |
Attivazione condizionale di variabili, intervalli e vincoli
E’ possibile attivare e disattivare variabili, intervalli e vincoli a seconda della verità di alcune condizioni.
Si vuole modellare la quantità prodotta da un macchinario tenendo conto del fatto che esso possa essere acceso o spento. Nel primo caso questo potrà produrre una quantità positiva non infinita mentre nel secondo la produzione sarà nulla.
Si indica con y \in \{0, 1\} lo stato di accensione del macchinario e con x \in \mathbb{R}^+ la quantità da esso prodotta. Per modellare tale situazione si può dire che
\begin{cases} y = 0 \implies x \le 0\\ y = 1 \implies x \le M \end{cases}
che può essere riscritto come x \le My.
Il genere di approssimazione visto nell’esempio si chiama big-M constraint ed è necessario per non cadere nell’utilizzo di valori quali \infty che non sono facilmente trattabili (ovviamente M deve di un ordine di grandezza sufficientemente grande/piccolo per non rischiare di escludere una soluzione ma non talmente grande/piccolo da essere difficile da trattare).
E’ possibile anche accendere e spegnere vincoli di appartenenza ad un intervallo:
\begin{cases} y = 0 \implies x = 0 \\ y = 1 \implies x \in [a, b] \end{cases}
diventa
\begin{cases} x \ge ay \\ x \le by \end{cases}
In generale, è necessario trovare un vincolo in funzione della variabile booleana che lo controlla e fare in modo che tale vincolo diventi ridondante (ad esempio qualcosa come 0 = 0) in caso questo debba essere spento.
E’ possibile spegnere vincoli nella loro interezza seguendo la stessa logica.
Si vuole attivare il vincolo 3x_1 + 4x_2 - 7x_3 \le 11 solo nel caso in cui y_1 = 1 (con x_1 \in [1, 3], x_2 \in \{0, 1\}, x_3 \in [-2, 6]).
Nel “caso peggiore” l’espressione vale 27 dunque si può scrivere che \begin{align} 3x_1 + 4x_2 - 7x_3 &\le \begin{cases} 11 & y_1 = 1 \\ 27 & y_1 = 0 \end{cases} \\ &= 27 - 16y_1 \end{align}
Ottimizzazione di problemi min-max, max-min e min-abs
Un problema è detto di min-max se è della forma
\begin{align*} \min & \qquad \max\{e_1, e_2, \dots, e_n\}\\ \text{s.t.} & \qquad x \in X \end{align*}
dove le varie e_i sono funzioni nelle variabili di controllo. La definizione è analoga per i problemi di max-min.
In caso di problemi di min-max si ha che la funzione da minimizzare non è lineare in quanto la funzione \max non è lineare. In casi del genere, si introduce un nuova variabile y e, nei vincoli, si aggiunge che y \ge e_1, y \ge e_2, \dots, y \ge e_n. Per il problemi di max-min, il procedimento è analogo.
Il massimo di un insieme di funzioni convesse, è a sua volta convessa.
Un problema è detto di min-abs se è della forma
\begin{align} \min \qquad & |e| \\ \text{s.t.} \qquad & x \in X \end{align}
dove e è una funzione nelle variabili di controllo.
Anche nel caso di problemi di min-abs la funzione da minimizzare non è lineare, dunque la si sostituisce con una variabile y e, nei vincoli, si impone che y \ge e e che y \ge -e. Questo procedimento è giustificato dal fatto che |e| = \max\{e, -e\}.
Forma standard e forma generale
Sia dato un problema di ottimizzazione lineare generico come il seguente: \begin{align*} \max & \qquad \sum_{j=1}^n c_jx_j\\ \text{s.t.} & \qquad \sum_{j=1}^n a_{ij} x_j \le b_i \qquad \forall i = 1 \dots m \end{align*} Lo stesso problema è esprimibile in in modo vettoriale: \begin{align*} \max & \qquad c^Tx \\ \text{s.t.} & \qquad Ax \le b \qquad \end{align*} dove A = (a_{ij}) con i = 1 \dots m e j = 1 \dots n, c = (c_1, c_2, \dots, c_n)^T e b = (b_1, b_2, \dots, b_m)^T.
Da ciò deriva che tutte le soluzioni ammissibili per il problema generico sono x^* : Ax^* \le b mentre x^* \in \mathbb{R}^n è ottimo se Ax^* \le b e se \not \exists \overline x : A \overline x \le b \land c^T\overline x \gt c^Tx^*. Deriva anche che un problema è inammissibile se \not \exists \overline x : A \overline x \le b e che un problema è illimitato se \forall M \gt 0 \exists \overline x : A \overline x \le b \ c^T\overline x \gt M.
Dato che i problemi di ottimizzazione lineare sono problemi convessi, tutti gli ottimi locali sono anche ottimi globali.
Ci possono essere più soluzioni ottime, tutte che portano la funzione obiettivo allo stesso valore, ne basta trovare una.
Un problema in forma standard è espresso come: \begin{align*} \min & \qquad c^Tx \\ \text{s.t.} & \qquad Ax = b \\ & \qquad x \ge 0 \end{align*} Il primo vincolo restituisce un sottospazio affine mentre il secondo restituisce un cono.
Un problema espresso in forma generale è espresso come: \begin{align*} \max & \qquad c^Tx \\ \text{s.t.} & \qquad Ax \le b \qquad \end{align*} L’insieme ammissibile di un qualsiasi problema di ottimizzazione lineare è un poliedro.
Le dimensioni degli oggetti in questione sono A \in \mathcal M_\mathbb{R}(m, n) b \in \mathbb{R}^m, c \in \mathbb{R}^n.
Entrambe le forme sono equivalenti e qualunque problema può essere riformulato in forma standard e anche in forma generale.
Per trasformare un problema di ottimizzazione lineare in forma standard o in forma generale, si faccia riferimento alla seguente tabella:
| Cosa | Forma standard | Forma generale |
|---|---|---|
| a^Tx \le b | a^Tx + s = b, s \ge 0 | \checkmark |
| a^Tx = b | \checkmark | a^Tx \le b, -a^Tx \le -b |
| a^Tx \ge b | a^Tx - s = b, s \ge 0 | -a^Tx \le -b |
| \min c^Tx | \checkmark | -\max -c^Tx |
| x \ge 0 | \checkmark | -x \le 0 |
| x libera | x:=x^*-x^-, x^*+ \ge 0, x^- \ge 0 | \checkmark |
| x \le 0 | Sostitutizione di x con -\overline x, \overline x \ge 0 | \checkmark |
Per risolvere un semplice problema in due variabili in forma generale, è prima necessario rappresentare il poliedro che rispetta i vincoli, poi serve trovare il gradiente della funzione da massimizzare. Sia f(x_1, x_2) la funzione da massimizzare, se impongo f(x_1, x_2) = \alpha trovo la retta, perpendicolare al gradiente, di tutti i punti nei quali la funzione f valutata restituisce \alpha. L’obiettivo è trovare il più alto \alpha tale per cui la retta contiene almeno un punto che appartiene all’insieme ammissibile.
Lo stesso ragionamento è analogo in tre dimensioni con un piano al posto della retta.
Poliedri
L’insieme \left\{x \in \mathbb{R}^n : a^Tx \le b\right\} è un semispazio chiuso di \mathbb{R}^n.
Un poliedro in \mathbb{R}^n è l’intersezione di un numero finito di semispazi chiusi.
Un politopo è un poliedro limitato e non vuoto, cioè P \ne \emptyset e \exists M \gt 0 : \forall x \in P \ x_i \in [-M, M] \forall i = 1 \dots n
Di un poliedro, sono interessanti i vertici e la direzione di recessione.
Un vertice di un poliedro P \subseteq \mathbb{R}^n è un vettore r \in \mathbb{R}^n che non si può esprimere come una combinazione convessa di altri vettori di P, ovvero \not \exists (x', x'' \in P, \lambda \in (0, 1)) : v = \lambda x' + (1 - \lambda) x''.
Intuitivamente, i vertici di un poliedro sono le “punte”.
Una direzione di recessione per un poliedro P \subseteq \mathbb{R}^n è un vettore di \mathbb{R}^n tale per che \forall x \in P \ \forall \lambda \ge 0 \ x + \lambda d \in P.
Intuitivamente, la direzione di recessione è una direzione tale per cui, partendo da un punto qualsiasi e procedendo in tale direzione, non si esce mai dal poliedro.
P = \mathbb{R}^{n+} è un poliedro e l’insieme di tutte le direzioni di recessione è proprio \mathbb{R}^{n+} e l’unico vertice è l’origine.
P = \mathbb{R}^n è un poliedro e l’insieme di tutte le direzioni di recessione è proprio \mathbb{R}^n e non ha vertici.
P = \left\{x \in \mathbb{R}^{2+} : x_1 + x_2 \le 1\right\} è un poliedro limitato, dunque non ha direzioni di recessione.
P = \left\{ x \in \mathbb{R}^{2+} : x_2 \ge x_1, x_2 \le 2x_1 \right\} ha un solo vertice (l’origine) e ha infinite direzioni di recessione e l’insieme delle direzioni di recessione è dato da P.
Per comprendere gli esempi, può essere utile disegnarli su diun piano cartesiano.
Se un problema descrive un poliedro limitato allora anche il problema è limitato o, al massimo, inammissibile.
Se esiste una soluzione ottima allora ne esiste una che è anche un vertice.
Scomposizione di poliedri
Dati due insiemi A, B \subseteq \mathbb R^n, la somma di insiemi A+B è un insieme C \subseteq \mathbb R^n tale che
C = \left\{ x \in \mathbb R^n : \left( \exists x' \in A, x'' \in B : x = x' + x'' \right) \right\}
La somma di insiemi convessi è convessa.
Dato un poliedro P, allora \exists V = \{v^1, v^2, \dots, v^n\} \subseteq \mathbb R^n, W = \{w^1, w^2, \dots, w^r\} \subseteq \mathbb R^n tali che P = \text{conv}(V) + \text{cone}(W) dove V è l’insieme dei vertici del poliedro, W è un insieme di direzioni, \text{conv} indica l’inviluppo convesso e \text{cone} indica l’inviluppo conico.
To be continued.